class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)

        # dp[i][j] 表示 word1 的前 i 个字符到 word2 的前 j 个字符的编辑距离
        # dp 数组的大小为 (n1+1) x (n2+1)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]

        # 初始化 dp 数组
        # 将 word1 的前 i 个字符转换为空字符串，需要 i 次删除
        for i in range(n1 + 1):
            dp[i][0] = i

        # 将空字符串转换成 word2 的前 j 个字符，需要 j 次插入
        for j in range(n2 + 1):
            dp[0][j] = j

        # 填充 dp 数组
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                # 如果当前字符相同
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                # 如果当前字符不同
                else:
                    dp[i][j] = min(dp[i][j - 1],  # 插入操作
                                   dp[i - 1][j],  # 删除操作
                                   dp[i - 1][j - 1]) + 1  # 替换操作

        return dp[n1][n2]

# if __name__ == '__main__':
#     print(Solution().minDistance("horse", "ros"))
import sys

# 实例化 Solution 类
sol = Solution()

# 读取 word1
word1 = sys.stdin.readline().strip()
# 读取 word2
word2 = sys.stdin.readline().strip()

# 调用方法计算编辑距离
result = sol.minDistance(word1, word2)

# 输出结果
print(result)

